import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/*
 * @lc app=leetcode.cn id=301 lang=java
 *
 * [301] 删除无效的括号
 */

// @lc code=start
class Solution {
    Set<String> set = new HashSet<>();
    int n, max, len;
    public List<String> removeInvalidParentheses(String s) {
        //返回所有可能的结果. return all ans.
        n = s.length();
        int l = 0, r = 0;
        for(char c : s.toCharArray()){
            if(c == '('){
                ++l;
            }
            if(c == ')'){
                ++r;
            }
        }
        max = Math.min(l, r);
        //使用dfs进行回溯
        dfs(0,"",0,s);
        return new ArrayList<>(set);
    }
    void dfs(int u, String cur, int score, String s){
        //左括号得分1, 右括号得分-1
        // if score < 0 : 字串前缀中[右括号数量] > [左括号数量]
        // if score < max : 最大得分  一定是左括号全部出现在左边   右括号再逐一匹配 
        //                  所以最大得分不可能超过右括号的数量,也不可能超过左括号的数量;(因为最终得分要为0才是合法值)
        //                  相当于完成了一次剪枝 
        if(score < 0 || score > max) return ;
        if(u == n){
            //遍历结束时,得分为0且当前字串长度 >= 已保存字串长度
            if(score == 0 && cur.length() >= len){
                if(cur.length() > len){
                    ///当前字串长度 > 已保存字串长度,说明具有更优解(删除最小数量),清空set
                    set.clear();
                }
                //对len重新赋值
                len = cur.length();
                set.add(cur);
            }
            return ;
        }
        char c= s.charAt(u);
        //String.valueOf(c) 返回参数c类型的字符串表现形式
        //因为字符串只能与字符串相加,因此先将字符转换成字符串形式
        //括号只有两种可能,要么加入要么不加入;字母一定加入
        if(c == '('){
            dfs(u + 1, cur + String.valueOf(c), score + 1, s);
            dfs(u + 1, cur, score, s);
        }
        else if(c == ')'){
            dfs(u + 1, cur + String.valueOf(c), score - 1, s);
            dfs(u + 1, cur, score, s);
        }
        else{
            dfs(u + 1, cur + String.valueOf(c), score, s);
        }
    }
}
// @lc code=end

